Algorithme LLL
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
top
L’algorithme LLL, des initiales de A. Lenstra, H. Lenstra et L. Lovász, est un algorithme de réduction de réseau qui s'exécute en temps polynomial.
Contents
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Présentation
L'algorithme LLL procède à une réduction de base de réseau. Il prend en entrée un nombre d de vecteurs de base d'un réseau, tels que ces vecteurs soient de dimension n et de norme inférieure à B, et retourne en sortie une base de réseau LLL-réduite, c'est-à-dire presque orthogonale, en temps O ( d 5 n log 3 B ) {\displaystyle O(d^{5}n\log ^{3}B)\,} .
Pseudo-code
L'algorithme LLL repose sur l'algorithme de réduction faible de bases, qui permet de rendre une base presque orthogonale.
Entrée : Une base
B
=
(
e
1
,
.
.
.
,
e
n
)
{\displaystyle B=(e_{1},...,e_{n})}
Sortie : Une base réduite issue de
B
{\displaystyle B}
LLL(B):
B =
(
e
1
,
.
.
.
,
e
n
)
←
{\displaystyle (e_{1},...,e_{n})\leftarrow }
ReducFaible(B)
*On fait Gram-Schmidt*
Pour i=1 à n :
Pour j= 1 à i-1 :
a
i
,
j
←
<
e
i
,
e
j
>
<
e
j
,
e
j
>
{\displaystyle a_{i,j}\leftarrow {\dfrac {<e_{i},e_{j}>}{<e_{j},e_{j}>}}}
e
i
←
e
i
−
∑
j
<
i
a
i
,
j
e
j
{\displaystyle e_{i}\leftarrow e_{i}-\sum _{j<i}a_{i,j}e_{j}}
Si B est réduite
retourne B
Sinon
i
←
m
i
n
(
{
j
∈
[
1
,
n
]
|
|
|
e
j
+
1
+
a
j
+
1
,
j
e
j
|
|
2
<
3
4
|
|
e
j
|
|
2
}
)
{\displaystyle i\leftarrow min(\lbrace j\in [1,n]~|~||e_{j+1}+a_{j+1,j}e_{j}||^{2}<{\dfrac {3}{4}}||e_{j}||^{2}\rbrace )}
echanger(
e
i
{\displaystyle e_{i}}
,
e
i
+
1
{\displaystyle e_{i+1}}
)
retourne LLL(B)
Applications
À l'origine, les applications consistaient en la production d'un algorithme de factorisation des polynômes à coefficients rationnels en produits de polynômes irréductibles, ainsi qu'en la résolution des problèmes d'optimisation linéaire avec solutions entières et dimensions fixes. D'autres applications ont été découvertes en cryptographiecite-ref-1[1], notamment en cryptographie à clé publique, par exemple avec RSA, les cryptosystèmes basés sur le problème du sac à dos et NTRUEncrypt. En particulier l'algorithme LLL a rendu inefficaces tous les cryptosystèmes utilisant le problème du sac à doscite-ref-boyer-2-0[2]. Il sert également dans le cas des réseaux euclidiens.
Notes et références
(en)
Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé
«
Lenstra–Lenstra–Lovász lattice basis reduction algorithm
»
(
voir la liste des auteurs
)
.
cite-note-11. ↑ nitajabderrahmane-nitajAbderrahmane Nitaj, « Applications de l'algorithme LLL en cryptographie », sur Département de Mathématiques et Mécanique de l'Université de Caen Basse Normandie (UCBN).
Bibliographie
• lenstra-h-lenstra-et-l-lov-sz1982a-lenstra-h-lenstra-et-l-lov-sz1982(en) A. Lenstra, H. Lenstra et L. Lovász, « Factoring polynomials with rational coefficients », Mathematische Annalen, vol. 261, no 4, 1982, p. 515–534 (DOI 10.1007/BF01457454, MR 0682664, lire en ligne)
• (en) Peter Borwein, Computational Excursions in Analysis and Number Theory, Springer, 2002 (ISBN 978-0-387-95444-8) : contient une description complète de l'algorithmes ainsi que des implémentations en pseudocode
• roland-boyer-ivan2007abuaf-roland-boyer-ivan2007Abuaf Roland, Boyer Ivan, « Factorisation dans Z [ X ] {\displaystyle \mathbb {Z} [X]} », Exposé de maîtrise proposé par François Loeser, 20 juin 2007 (lire en ligne)
• Portail de la cryptologie
• Portail de l'informatique théorique